백준 5670번
오늘 풀어본 문제는 백준의 5670번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
휴대폰에서 길이가 $P$ 인 영단어를 입력하려면 버튼을 $P$ 번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다.
- 모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력해야 한다.
- 길이가 $1$ 이상인 문자열 $c_1 c_2 \cdots c_n$ 이 지금까지 입력되었을 때, 사전 안의 모든 $c_1 c_2 \cdots c_n$ 으로 시작하는 단어가 $c_1 c_2 \cdots c_n c$ 로도 시작하는 글자 $c$ 가 존재한다면 모듈은 사용자의 버튼 입력 없이도 자동으로 $c$를 입력해 준다. 그렇지 않다면 사용자의 입력을 기다린다.
예를 들면, 사전에 “hello”, “hell”, “heaven”, “goodbye” 4개의 단어가 있고 사용자가 “h”를 입력하면 모듈은 자동으로 “e”를 입력해 준다. 사전상의 “h”로 시작하는 단어들은 모두 그 뒤에 “e”가 오기 때문이다. 그러나 단어들 중 “hel”로 시작하는 것도, “hea”로 시작하는 것도 있기 때문에 여기서 모듈은 사용자의 입력을 기다린다. 이어서 사용자가 “l”을 입력하면 모듈은 “l”을 자동으로 입력해 준다. 그러나 여기서 끝나는 단어인 “hell”과 그렇지 않은 단어인 “hello”가 공존하므로 모듈은 다시 입력을 기다린다. 사용자가 “hell”을 입력하기 원한다면 여기서 입력을 멈출 것이고, “hello”를 입력하기 원한다면 직접 “o” 버튼을 눌러서 입력해 줘야 한다. 따라서 “hello”를 입력하려면 사용자는 총 3번 버튼을 눌러야 하고, “hell”, “heaven”은 2번이다. “heaven”의 경우 “he”에서 “a”를 입력하면 바로 뒷부분이 모두 자동으로 입력되기 때문이다. 비슷하게, “goodbye”는 단 한 번만 버튼을 눌러도 입력이 완료될 것이다. “g”를 입력하는 순간 뒤에 오는 글자가 항상 유일하므로 끝까지 자동으로 입력되기 때문이다. 이때 사전에 있는 단어들을 입력하기 위해 버튼을 눌러야 하는 횟수의 평균은 $(3 + 2 + 2 + 1)/4 = 2.00$이다.
사전이 주어졌을 때, 이 모듈을 사용하면서 이와 같이 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에 사전에 속한 단어의 개수 $N$이 주어지며 $(1 \leq N \leq 105)$, 이어서 $N$ 개의 줄에 $1 \sim 80$ 글자인 영어 소문자로만 이루어진 단어가 하나씩 주어진다. 이 단어들로 사전이 구성되어 있으며, 똑같은 단어는 두 번 주어지지 않는다. 각 테스트 케이스마다 입력으로 주어지는 단어의 길이 총합은 최대 $106$ 이다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 문제의 정답을 소수점 둘째 자리까지 반올림하여 출력한다.
풀이과정
1번째 시도
이 문제는 Trie 을 사용하여 해결할 수 있는 문제이다. Trie 는 여러 개의 문자열들을 효과적으로 관리할 수 있게 도와주는 자료 구조로, 원하는 문자열이나 문자열의 ‘prefix’를 빠르게 탐색할 수 있다는 장점이 있다.
이 문제에서 Trie 를 활용한 방식은 단어들이 입력을 받을 때마다 Trie 와 벡터에 저장하고, 입력을 모두 받으면 각 단어들을 확인하면서 버튼을 눌러야 하는 횟수를 확인하면 된다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
struct TrieNode {
bool endOfWord;
int next[26];
int nextLetters;
TrieNode() : endOfWord(false), nextLetters(0) {
for (int i = 0; i < 26; i++) {
next[i] = -1;
}
}
};
struct Trie {
vector<TrieNode> nodes;
Trie() {
nodes.push_back(TrieNode());
}
void add(const string& stringToAdd) {
int currentNode = 0;
for (char c : stringToAdd) {
int idx = c - 'a';
if (nodes[currentNode].next[idx] == -1) {
nodes[currentNode].nextLetters++;
nodes[currentNode].next[idx] = nodes.size();
nodes.push_back(TrieNode());
}
currentNode = nodes[currentNode].next[idx];
}
nodes[currentNode].endOfWord = true;
}
};
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed;
cout.precision(2);
while (true) {
int N;
string tempWord;
vector<string> words;
Trie trie;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> tempWord;
words.emplace_back(tempWord);
trie.add(tempWord);
}
int totalPush = 0;
for (const string& word : words) {
int pushCount = 0;
int currentNode = 0;
for (int i = 0; i < word.length(); i++) {
if (i == 0 || trie.nodes[currentNode].endOfWord == true || trie.nodes[currentNode].nextLetters > 1) {
pushCount++;
}
currentNode = trie.nodes[currentNode].next[word[i] - 'a'];
}
totalPush += pushCount;
}
cout << static_cast<double>(totalPush) / words.size() << "\n";
}
return 0;
}
실행 결과 ‘출력 초과’ 가 떴다.
2번째 시도
PS 인생 ‘출력 초과’ 는 처음 보는 종류의 오류였다. 일단 오류의 이름으로 미루어 보아 출력하는 과정에서 문제가 생겼다는 걸 추측할 수 있었고, 루프 문을 무한 루프로 한 것이 문제일지도 모른다고 생각했다.
질문 게시판을 살짝 둘러본 결과, while 문의 조건으로 true 를 넣어 무한 루프를 넣는 대신 cin >> N 을 넣으면 정상적으로 작동하는 것을 알게되었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
struct TrieNode {
bool endOfWord;
int next[26];
int nextLetters;
TrieNode() : endOfWord(false), nextLetters(0) {
for (int i = 0; i < 26; i++) {
next[i] = -1;
}
}
};
struct Trie {
vector<TrieNode> nodes;
Trie() {
nodes.push_back(TrieNode());
}
void add(const string& stringToAdd) {
int currentNode = 0;
for (char c : stringToAdd) {
int idx = c - 'a';
if (nodes[currentNode].next[idx] == -1) {
nodes[currentNode].nextLetters++;
nodes[currentNode].next[idx] = nodes.size();
nodes.push_back(TrieNode());
}
currentNode = nodes[currentNode].next[idx];
}
nodes[currentNode].endOfWord = true;
}
};
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed;
cout.precision(2);
int N;
while (cin >> N) {
string tempWord;
vector<string> words;
Trie trie;
for (int i = 0; i < N; i++) {
cin >> tempWord;
words.emplace_back(tempWord);
trie.add(tempWord);
}
int totalPush = 0;
for (const string& word : words) {
int pushCount = 0;
int currentNode = 0;
for (int i = 0; i < word.length(); i++) {
if (i == 0 || trie.nodes[currentNode].endOfWord == true || trie.nodes[currentNode].nextLetters > 1) {
pushCount++;
}
currentNode = trie.nodes[currentNode].next[word[i] - 'a'];
}
totalPush += pushCount;
}
cout << static_cast<double>(totalPush) / words.size() << "\n";
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
오늘 푼 문제도 세미나에서 배운 내용을 바탕으로 한 문제였다. 문자열을 다루는 여러 가지 방법에 대한 세미나였고 Trie는 그 과정에서 배운 자료 구조였다. 이 문제를 푸는데 어려웠던 부분은 Trie 를 구현하는 것이었다. Trie 를 한 번 만들고 나서 문제의 조건에 맞게 사용하는 것은 그렇게 어렵지 않았다.
앞으로도 Trie를 사용해야 하는 문제를 종종 만나게 될 것 같다는 생각이 들어 내 백준 문제 풀이들을 저장해두는 repository 에 폴더2를 만들어 직접 구현한 Trie 를 저장해두었다. PS를 해나가며 만들게 될 자료 구조들도 저장할 것이고, 해당 자료 구조들을 사용해야 하는 문제들을 다시 만나게 되면 코드를 repository 에서 가져와 수정하여 사용할 수 있을 것이다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/5670
2: https://github.com/ChoiCube84/baekjoon-solutions/tree/main/C%2B%2B/custom_data_structures